class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int begin = Integer.MIN_VALUE / 4;
        int end = Integer.MAX_VALUE / 4;
        int tail = Integer.MIN_VALUE;
        //堆里存的是长度为3的数组，分别是 值，所在nums中的下标，所在nums中的list的下标
        Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];//从小到大排序
            }
        });
        for(int i=0;i<nums.size();i++){
            tail = Math.max(tail,nums.get(i).get(0));
            queue.offer(new int[]{nums.get(i).get(0),i,0});
        }
        while(!queue.isEmpty()){
//            var top = queue.poll();
            int[] top = queue.poll();
            int value = top[0];
            int listIndex = top[1];
            int elementIndex = top[2];
            if(tail - value < end - begin){ //更新区间的左右端点
                begin = value;
                end = tail;
            }
            //下一个元素入队列
            if(elementIndex+1 >= nums.get(listIndex).size()){ //一旦越界，说明当前如果继续收缩，至少当前所在的子数组，它的
                //所有数据都不会被左右区间包含
                break; //收缩的太狠了，虽然长度短了，但是部分元素没有包含进去
            }
            top[0] = nums.get(listIndex).get(1+elementIndex);
            top[2] = 1+elementIndex;
            queue.offer(top);
            //更新tail，要维护堆中的最大元素
            tail = Math.max(tail,nums.get(listIndex).get(1+elementIndex));
        }
        return new int[]{begin,end};
    }
}

// 1.左边界和右边界一定出现在nums中,否则有收缩的余地
// 2.尽量让r - l 的结果偏小
// 3.需要对所有元素排序
// 4.结果在这个序列里   [0，4，5，9，10,.....20,...24]
// 5.因为是部分有序，所以我们可以借助一些数据结构，避免额外的排序
// 6.借用了堆（优先队列） 构造小顶堆
// 7.判断队尾-队头，如果满足条件，更新答案